# 1.数据结构定义
#     1.名词定义：数据结构是指相互之间存在着一种或多种关系的数据元素的集合和该集合中数据元素之间的关系组成。记为：Data_Structure=(D,R)，其中D是数据元素的集合，R是该集合中所有元素之间的关系的有限集合。
#     2.其它定义
#         1.Sartaj Sahni在他的《数据结构、算法与应用》一书中称：“数据结构是数据对象，以及存在于该对象的实例和组成实例的数据元素之间的各种联系。这些联系可以通过定义相关的函数来给出。”他将数据对象（data object）定义为“一个数据对象是实例或值的集合”。
#         2.Clifford A.Shaffer在《数据结构与算法分析》一书中的定义是：“数据结构是ADT（抽象数据类型Abstract Data Type） 的物理实现。”(意思是抽象数据类型的概念都需要借助数据结构来进行实现)
#         3.Robert L.Kruse在《数据结构与程序设计》一书中，将一个数据结构的设计过程分成抽象层、数据结构层和实现层。其中，抽象层是指抽象数据类型层，它讨论数据的逻辑结构及其运算，数据结构层和实现层讨论一个数据结构的表示和在计算机内的存储细节以及运算的实现。
#     数据结构具体指同一类数据元素中，各元素之间的相互关系，包括三个组成成分，数据的逻辑结构，数据的存储结构和数据运算结构。
#     3.数据结构，是各大计算机编程语言的基本理论。通俗点讲，数据结构是各种编程语言理论的抽象性概念。数据结构适用于任何一种编程语言。
#
# 2.算法：
#     是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。
#
#     算法中的指令描述的是一个计算，当其运行时能从一个初始状态和（可能为空的）初始输入开始，经过一系列有限而清晰定义的状态，最终产生输出并停止于一个终态。一个状态到另一个状态的转移不一定是确定的。
#
# 3.Pascal之父——Nicklaus Wirth(尼古拉斯·沃斯)的至理名言：程序 = 数据结构 + 算法
#     这个公式对计算机科学的影响程度足以类似物理学中爱因斯坦的相对论e = mc^2，即，一个公式说明了程序的本质
#     该公式可以继续细化为如下：
#         问题 --> 数据结构 + 算法 == 程序 -->解决问题
#
# 4.抽象数据类型
#     1.全称：Abstract Data Type
#     2.简称：ADT
#     3.定义：
#         1.是指一个数学模型以及定义在此数学模型上的一组操作。抽象数据类型需要通过固有数据类型（高级编程语言中已实现的数据类型）来实现。抽象数据类型是与表示无关的数据类型，是一个数据模型及定义在该模型上的一组运算。对一个抽象数据类型进行定义时，必须给出它的名字及各运算的运算符名，即函数名，并且规定这些函数的参数性质。一旦定义了一个抽象数据类型及具体实现，程序设计中就可以像使用基本数据类型那样，十分方便地使用抽象数据类型(来自百度百科).
#         2.通俗解释：最开始的计算机语言，关注的都是如何更加有效率地计算，可以说其目的是计算层面的抽象。然而随着这个行业的不断发展，计算机不仅仅用于计算，开发也不仅只关注计算过程了，数据层面的抽象也变得同样重要。虽然计算机语言一开始就有对数据的抽象，但是那些都只是对一些最基本的数据类型而不包括我们想要用的，多种多样的数据。
#
#         程序处理的数据，通常是不同的类型的。只有事先约定好的不同类型的数据的存储方式，计算机才能正确理解逻辑上不同的数据类型。所有编程语言都会有一组内置的基本数据类型。另外在实际工作过程中，或早或晚总会碰到一些没法用现有数据类型解决的问题，这时就需要自定义一些数据类型来解决。像Python这样比较高级的语言的话，在基本类型的基础上还添加了一些额外的数据结构如tuple,list,dict（这些如果从广义上来说也算是Python的数据类型）。
#
#         以上基本数据类型都是比较simple的结构，但是他们具有一个共通的问题，就是都会把数据暴露在外。这点类似于一个人如果有了对某个变量的权限的话他就可以看到这个变量代表的数据结构中的所有数据。而如果我们不希望被看到，那么这个问题可能就比较严重了。为了解决这个问题，就必须要有一种数据类型，它可以让使用者只需要考虑如何去使用，而不需要去关注类型内部的具体实现方式以及数据的表示等等。这样的类型从概念上来说就是抽象数据类型了。
#     4.抽象数据类型的实现思路
#         基本思想均是把数据定义为抽象的数据对象集合，只为他们定义可用的合法操作，而不暴露具体的内部细节，注意，不论是操作细节还是数据存储细节均不暴露。
#
#         基于这种思路，一般而言，抽象数据类型应该至少具备以下三种操作：
#             1.构造操作，即如何通过抽象数据类型创建抽象数据对象
#             2.解析操作(也可理解为获取操作)：一定会有一系列getXXX()方法去获取到该抽象类型内部的任意数据及操作
#             3.修改操作：一定会有一系列setXXX()方法去给当前抽象数据类型修改任意数据及操作。
#     5.可变类型与不可变类型：基于以上的三种基本操作，可以判断一个数据类型的可变性。
#         如果一个类型同时具备以上三种类型，那么这个类型就是可变的。
#         如果一个类型只具备一二两种操作，那么这个类型就是不可变的。
#
# 5.抽象数据类型在Python中的实际应用：面向对象编程(Object Oriented Programming,简称OOP)
#

# 6.线性表
#     1.定义
#         线性表（linear list）是数据结构的一种，一个线性表是n个具有相同特性的数据元素的有限序列。数据元素是一个抽象的符号，其具体含义在不同的情况下一般不同。线性表在数学概念中，其本质是一个集合。
#
#         在稍复杂的线性表中，一个数据元素可由多个数据项（item）组成，此种情况下常把数据元素称为记录（record），含有大量记录的线性表又称文件（file）。
#
#         线性表中的个数n定义为线性表的长度，n = 0 时称为空表。在非空表中每个数据元素都有一个确定的位置，如用ai表示数据元素，则i称为数据元素ai在线性表中的位序。
#
#         线性表的相邻元素之间存在着序偶关系。如用（a1，…，ai-1，ai，ai+1，…，an）表示一个顺序表，则表中ai - 1 领先于ai，ai领先于ai+1，称ai - 1 是ai的直接前驱元素，ai + 1 是ai的直接后继元素。当i=1,2，…，n - 1 时，ai有且仅有一个直接后继，当i=2，3，…，n时，ai有且仅有一个直接前驱。
#
#     2.分类
#         1.预先注意：我们说“线性”和“非线性”，只在逻辑层次上讨论，而不考虑存储层次，所以双向链表和循环链表依旧是线性表。
#         2.逻辑层面划分：在数据结构逻辑层次上细分，线性表可分为一般线性表和受限线性表。一般线性表也就是我们通常所说的“线性表”，可以自由的删除或添加结点。受限线性表主要包括栈和队列，受限表示对结点的操作受限制。
#         3.表示层面(实在想不明白的就按照存储层面)划分：在表示层面，线性表主要分为顺序表示和链式表示，即我们常说的线性表的顺序存储和链式存储。
#         4.顺序表示：指的是用一组地址连续的存储单元依次存储线性表的数据元素，称为线性表的顺序存储结构或顺序映像（sequential mapping）。它以“物理位置相邻”来表示线性表中数据元素间的逻辑关系，可随机存取表中任一元素。
#         5.链式表示：指的是用一组任意的存储单元存储线性表中的数据元素，称为线性表的链式存储结构。它的存储单元可以是连续的，也可以是不连续的。在表示数据元素之间的逻辑关系时，除了存储其本身的信息之外，还需存储一个指示其直接后继的信息（即直接后继的存储位置），这两部分信息组成数据元素的存储映像，称为结点（node）。它包括两个域；存储数据元素信息的域称为数据域；存储直接后继存储位置的域称为指针域。指针域中存储的信息称为指针或链。
#
#     3.线性表的特征
#         1.集合中必存在唯一的'第一元素'
#         2.集合中必存在唯一的'最后元素'
#         3.除最后一个元素之外，均有唯一的后继(后件)
#         4.除第一个元素之外，均有唯一的前驱(前件)
#
#     4.线性表通用基本操作(注意：此为操作，并不是函数，任意操作名称对应某一种编程语言中规定的线性表的某一方法)
#         1）MakeEmpty(L) 这是一个将L变为空表的方法
#         2）Length（L） 返回表L的长度，即表中元素个数
#         3）Get（L，i） 这是一个函数，函数值为L中位置i处的元素（1≤i≤n）
#         4）Prior（L，i） 取i的前驱元素
#         5）Next（L，i） 取i的后继元素
#         6）Locate（L，x） 这是一个函数，函数值为元素x在L中的位置
#         7）Insert（L，i，x）在表L的位置i处插入元素x，将原占据位置i的元素及后面的元素都向后推一个位置
#         8）Delete（L，p） 从表L中删除位置p处的元素
#         9）IsEmpty(L) 如果表L为空表(长度为0)则返回true，否则返回false
#         10）Clear（L）清除所有元素
#         11）Init（L）同第一个，初始化线性表为空
#         12）Traverse（L）遍历输出所有元素
#         13）Find（L，x）查找并返回元素
#         14）Update（L，x）修改元素
#         15）Sort（L）对所有元素重新按给定的条件排序
#         16) strstr(string1,string2)用于字符数组的求string1中出现string2的首地址
#
#     5.线性表的结构特点
#         1.均匀性：我们规定：线性表中的任意元素可以为任意数据类型，但是，对于同一线性表而言，其各数据元素必须具有相同的数据类型和长度。
#         2.有序性：各数据元素在线性表中的位置只取决于它们的序号，数据元素之前的相对位置是线性的，即存在唯一的“第一个“和“最后一个”的数据元素，除了第一个和最后一个外，其它元素前面均只有一个数据元素(直接前驱)和后面均只有一个数据元素（直接后继）。
#
#     6.线性表的推广
#         1.时间有序表
#         2.排序表
#         3.频率有序表
#         4. ...
# 7.在Python中实现线性表的顺序存储——列表
#     1.专题讲解：使用Python实现线性表的顺序存储——列表。以下编码为模拟实现Python中的内建类——列表
class List(object):
    def __Locateitem__(self,value):
        if self.items[i] == value:
            return i
        self.size = size

    def __del__(self,value=None):
        for i in range(len(self.size)):
            self.items[i] = value

    def __setitem__(self,index,value):
        self.items[index] = value

    def __len__(self):
        return self.size

    def clear(self,value=None):
        for i in range(len(self.size)):
            self.items[i] = value

    def __iter__(self):
        for item in self.items:
            yield item

def test():
    size = 10
    l = List(size)
    l[0] = 1
    assert l[0] == 1

    l.clear()
    assert len(l) is None

del(l)


if __name__ == '__main__':
    test()
#
#     2.列表常用操作的时间复杂度计算
#         1.构造操作：上文说到，构造操作，即如何通过抽象数据类型创建抽象数据对象。其实就是指的创建操作。创建列表操作其时间复杂度为O(1)
#         2.增加操作：即向列表中追加一个元素。而Python中，对于列表的地址空间分配，是按照0,4,8,16,25, ...这样的规律进行分配的，即一开始会先分配四个空间。所以，如果一次分配够了足够的空间，即插入元素的数量没有超出空间限制的情况下，其时间复杂度为O(1)，当插入的元素的数量超出了上一次分配的空间范围，就要在内存中继续分配新的地址空间，进而时间复杂度就不在是O(1),会转为O(n)
#         3.插入操作：因为向列表中某一个位置前后插入任意一个操作，需要计算该位置前后下标，进而需要重新分配地址空间，所以平均下来插入操作的时间复杂度为O(n)
#         4.末尾追加操作：因为只是向列表的最后位置后添加一个元素，原理同增加操作一样，如果插入元素之后整体的元素数量没有超过现有的空间限制的话，时间复杂度为O(1),如果超出，需要继续重新分配地址空间的话，时间复杂度就为O(n)
#         5.删除操作：同插入操作，因为删除某一个元素，后续地址都要变化，所以平均下来时间复杂度为O(n)
#         6.获取操作：因为列表是用一组地址连续的存储单元依次存储线性表的数据元素，所以获取任意一个地址的元素，其时间复杂度为O(1)
#         7.排序操作：排序操作情况分为很多种，即每一种排序操作都对应某一种排序算法，所以，对于排序操作而言，其时间复杂度考察的就是每一种排序算法的时间复杂度
#     3.专题讲解：线性表的顺序存储结构重难点之——排序算法
#         1.预先补充一些基本概念
#             1.树：数据结构的一种，由n个有限节点组成的一个具有层次关系的集合。每个节点有0个或多个子节点。任意一颗树，都具有一个唯一的树根(根节点)
#             2.二叉树：每个结点最多有两个子结点的树就叫做二叉树
#             比如：有一个一维数组(python中用列表代替)0
#             将其用以下树形结构展示：
#                             3
#                     6               7
#                 2       3       5       6
#              7     8 9    5  4     3 6     7
#             此树即为二叉树
#             二叉树的子数有左右之分，顺序绝不能颠倒
#             3.节点：树中的任意一个元素即为树的节点
#             4.叶子节点：没有孩子的节点即为叶子节点
#             5.非叶子节点：有孩子的节点即为非叶子节点
#             6.完全二叉树：设二叉树的深度为h，除了h层外，其他各层(h-1)层结点数都达到了最大个数，第h层所有的结点都连续集中在最左边，就是一颗完全二叉树
#             7.堆：数据结构——树中，一类特殊的数据结构的总称。定义如下：n个元素的序列[k1,k2,k3,...ki,...,kn](i = 1,2,3,4,...,n/2),当且仅当满足以下条件：
#             (ki <= k2i,ki <= k2i+1)或>=时，就称之为堆。
#             注意：如果用一个列表存储一个堆，则该堆一定对应一个完全二叉树(堆的本质就是一棵树，一颗二叉树，一颗完全二叉树)。那么该完全二叉树的根结点就叫做堆的堆顶元素。
#             当此条件：(ki <= k2i,ki <= k2i+1)均为小于时，就会产生小顶堆，反之产生大顶堆。所以由堆的定义可以看出，第一个元素，即堆顶元素必为最小项或最大项，
#             同时，所有非叶子结点的值均不大于或不小于其子女的值
#             比如：
#                 大顶堆：[87,84,85,36,11,32]
#                             87
#                         84          45
#                     36      11  32
#                 小顶堆：[12,23,26,32,24,30,28,43,35]
#                                 12
#                             23          26
#                         32      24  30      28
#                     43      35
#             8.深度遍历优先算法：指代一种搜索算法，其算法核心是尽可能先对纵深方向进行搜索，当一条分支搜索到叶子结点后，终止，从左往右找到下一条分支，继续开始纵深方向的搜索，直至搜索到当前树的最后一个叶子节点，或不满足某一搜索条件时，终止。
#             9.广度遍历优先算法：指代一种搜素算法，其算法核心是针对树形结构的每一层，从根结点出发，按照一层一层的顺序，每层从左至右的顺序搜索，当搜索到某一层最后一个非叶子结点，结束该层搜索，进入下一层，继续搜索，直至搜索到最后一个叶子节点，或不满足某一搜索条件时，停止搜索。
#         2.顺序表的排序算法种类：八种常用排序算法，按照是否为线性时间角度出发分为两大类，按照实际应用角度出发分为四大类
#             1.是否为线性时间角度：
#                 1.非线性时间比较类算法：直接插入排序，希尔排序，冒泡排序，快速排序，简单选择排序，堆排序
#                 2.线性时间比较类算法：归并排序，基数排序
#                 注解：何为非线性时间：即算法的执行过程与时间上的先后顺序无关。何为线性时间：即算法的执行过程在时间上有先后之分。
#             2.实际应用角度：
#                 1.插入类排序：直接插入排序，希尔排序
#                 2.交换类排序：冒泡排序，快速排序
#                 3.选择类排序：简单选择排序，堆排序
#                 4.其他类排序：归并排序，基数排序
#         3.排序算法的时间复杂度：即描述一个算法的执行效率问题
#         以下表格为除了归并排序及基数排序之外剩余六种三大类排序算法的时间复杂度总结，做参考即可。
#                                     |        时间复杂度        |
#         类别        排序方法          平均      最好        最坏        稳定性
#         -------------------------------------------------------------------
#                     直接插入排序     O(n ^ 2)   O(n)       O(n ^ 2)     稳定
#         插入排序
#                     希尔排序       O(n ^ 3/2 )  O(n)       O(n ^ 2)    不稳定
#         -------------------------------------------------------------------
#                     冒泡排序        O(n ^ 2)    O(n)       O(n ^ 2)    稳定
#         交换排序
#                     快速排序      O(n log 2 n) O(n log 2 n)O(n ^ 2)    不稳定
#         -------------------------------------------------------------------
#                     简单选择排序    O(n ^ 2)   O(n ^ 2)    O(n ^ 2)    不稳定
#         选择排序
#                     堆排序        O(n log 2 n)O(n log 2 n)O(n log 2 n) 不稳定
#         -------------------------------------------------------------------
#
#         算法的稳定性：假定在待排序的列表中，存在多个相同的元素，若经过排序，这些想等元素的相对次序保持不变，即在原序列中，l[i] = l[i + 1]或l[i - 1] = l[i],且i-1 在 i 之前，i+1 在 i 之后，而在排序后的序列中，仍然为i-1 在 i 之前，i+1 在 i 之后，则称这种排序算法是稳定的，反之即为不稳定
#
#         在此，我们讲解具有代表性的不稳定算法：简单选择排序，以及两种常用的稳定性很好的算法：直接插入排序，冒泡排序。
#         其余排序算法，同学们自行研究，建议：好好研究一下堆排序。
#         4.选择排序之简单选择排序
#             1.思想：在需要排序的序列中选择最小的一个数与第一个数交换位置，在剩余的n-1个数中在选择一个最小的数与剩余n-1个数的序列中第一个元素交换位置，直至剩余元素个数为1，排序结束
#             2.算法实现步骤：
#                 1.遍历序列
#                 2.将每一次遍历取到的数和剩余n-1个数的序列中的第一个元素进行交换位置
#             排序算法代码示例如下：
#
# l = [3,1,5,7,2,4,9,6]
# for i in range(0, len(l)):
#     # 默认设置最小值的下标为当前值
#     min = i
#     # 在剩余n-1个元素的序列中找到最小元素的下标
#     for j in range(i + 1, len(l)):
#         # if l[i] > l[i+1]
#         # 如果找到，就把最小元素的下标赋值给min
#         if l[min] > l[j]:
#             min = j
#     # 将找到的最小值的元素和当前元素做位置交换
#     temp = l[min]
#     l[min] = l[i]
#     l[i] = temp
# print(l)
#
#         5.稳定性很好的算法：插入排序之——直接插入排序
#             1.思想：将一个记录插入到已排序好的有序表中，从而得到一个“新的”，记录数增1的有序表。
#             2.思路：先将第一个元素看作一个有序的子序列（说白了就是先把第一个元素假设单独放在一个序列里面，那么这个序列目前只有一个元素，当然就是已经有序了），然后从第二个元素开始依次进行插入，直至整个序列有序为止。
#             3.算法具体实现步骤：
#                 1.	先获得一个随机序列
#                 2.	拿出序列第一个元素后，从第二个开始用for循环遍历序列
#                 3.	定义一个循环变量j，该变量用来控制插入的位置，因为是后一个和前一个比较，所以让j = i-1
#                 4.	定义一个哨兵，专门用来临时存放元素
#                 5.	循环的让后一个元素和前一个元素比较，如果后一个元素比前一个元素小，就将其插入前一个元素之前。此时可能存在：已插入的元素仍然比前面某个元素小，所以，j -= 1，在比较一次，直至前面没有比自己大的元素，结束一次遍历
#                 6.	最终输出排序完成的列表即可。
#             排序算法示例代码如下：
# #初始化序列
# l = [45,34,78,78,98,23,12]
# # 拿出序列第一个元素后，从第二个开始用for循环遍历序列
# for i in range(1,len(l)):
#     # 后面的和前面的比较
#     j = i - 1
#     # 哨兵，临时存放元素
#     key = l[i]
#     # 每一次遍历决定插入的最终位置
#     while j >= 0:
#         # 如果后面的值小于前面的值
#         if key < l[j]:
#             # 后面的值赋值给前面的值，相当于交换位置
#             l[j+1] = l[j]
#             # 前面的值拿出来存在哨兵中
#             l[j] = key
#         # 继续向前比较
#         j -= 1
# print(l)
#
#         6.稳定性很好的算法：交换排序之——冒泡排序
#             1.算法思想：使用交换思想，即：前一个元素和后一个元素进行大小比较，如果前面比后面大，就交换位置，然后继续向后比较，直至一次冒泡结束，将最大值(或最小值)放到最后一个位置。通过多次的冒泡，最终实现排序
#             举例：
#             [9,7,5,3]                   [9,8,6,4,3]             ......
#             ---------                   ------------
#             [7,9,5,3]                   [8,9,6,4,3]
#             [7,5,9,3]                   [8,6,9,4,3]
#             [7,5,3,9]                   [8,6,4,9,3]             ......
#             ---------                   [8,6,4,3,9]
#             [5,7,3,9]                   ------------
#             [5,3,7,9]                   [6,8,4,3,9]
#             ---------                   [6,4,8,3,9]
#             [3,5,7,9]                   [6,4,3,8,9]             ......
#                                         ------------
#                                         [4,6,3,8,9]
#                                         [4,3,6,8,9]
#                                         ------------
#                                         [3,4,6,8,9]
#
#             通过以上的模拟冒泡排序的算法举例，可以总结出如下规律：
#                 1.n个元素的序列，总共需要冒泡n-1次
#                 2.设冒泡次数为i，那么每一次冒泡需要比较的次数就为n-i次
#
#             排序算法代码举例：
# import random
# import math
# l = []
# counts = int(input("请输入您想生成的序列的元素个数："))
# while True:
#     num = math.floor(random.random()*100+1)
#     l.append(num)
#     if len(l) == counts:
#         break
# print('排序前，生成好的随机列表为:%s'%l)
# for i in range(len(l)-1):
#     for j in range(len(l)-i-1):
#         if l[j] > l[j+1]:
#             temp = l[j]
#             l[j] = l[j+1]
#             l[j+1] = temp
# print("排序后的列表为：%s"%l)
#
#
#
#
#
#
#
#
# finally：书籍推荐
#     名称：数据结构(c语言版)
#     出版社：清华大学出版社
#     作者：严蔚敏、吴伟民


























